// 接雨水问题
#include <algorithm>
#include <cstdlib>
#include <stack>
#include <vector>
// 何时可以接到雨水？夹在i,j柱之间的柱子高度小于i柱和j柱中最小的那个
using namespace std;
int trap_1(vector<int> height) {
  // 解法一
  // 时间复杂度O(n)
  // 空间复杂度O(n)
  int n = height.size();
  vector<int> preMax(n, 0);
  vector<int> sufMax(n, 0);
  int i = 1, j = n - 2, p = height[0], s = height[n - 1];
  preMax[0] = height[0];
  sufMax[n - 1] = height[n - 1];
  while (i < n) {
    preMax[i] = max(height[i], preMax[i - 1]);
    sufMax[j] = max(height[j], sufMax[j + 1]);
    i++;
    j--;
  }
  int res = 0;
  for (int i = 0; i < n; i++) {
    res += (abs(preMax[i] - sufMax[i]) - height[i]);
  }
  return res;
}

int trap_2(vector<int> height) {
  // 解法二
  // 当左侧前缀最大值小于右侧后缀最大值时，左侧木桶可以计算盛水量，计算完成后，左侧可以向右扩展
  // 当右侧后缀最大值小于左侧前缀最大值时，右侧木桶可以计算盛水量，计算完成后，右侧可以向左扩展
  int n = height.size();
  int preMax = 0, sufMax = 0, l = 0, r = n - 1, res = 0;
  while (l < r) {
    preMax = max(preMax, height[l]);
    sufMax = max(sufMax, height[r]);
    if (preMax < sufMax) {
      res += (min(preMax, sufMax) - height[l]);
      l++;
    } else {
      res += (min(preMax, sufMax) - height[r]);
      r--;
    }
  }
  return res;
}